struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

//k个节点为一组反转链表，也可以解决3.cpp中的两两交换链表中的节点
class Solution {
    public:
        int len(ListNode*node)
        {
            int count=0;
            while(node)
            {
                count+=1;
                node=node->next;
            }
            return count;
        }
        ListNode* reverseKGroup(ListNode* head, int k) {
            int n=len(head);
            ListNode* dummy=new ListNode(-1,head);
            ListNode* p0=dummy, *pre=nullptr, *cur=head;
            for(;n>=k;n-=k)
            {
                for(int i=0;i<k;i++)
                {
                    //交换两个相邻节点的next指针指向
                    ListNode* nxt=cur->next;
                    cur->next=pre;
                    pre=cur;
                    cur=nxt;
                }
                //关键需要理解的点，这里理解了就不会有疑问了
                //原来是1->2->3->4->5（k=2）
                //实际没有在链表内交换节点的位置，只是修改了它们的next指针指向
                //交换后顺序没变，只是2的next指针指向了1，4的next指针指向了3
                //p0的next指针指向了2，从而后面的节点就可以连接起来了
    
                //两两交换后pre指向最后一个交换的节点，cur指向的是pre后面
                //的那个节点，由于我们改变的是一组中节点的指向，所以为了最后
                //输出的答案正确，我们需要确保第一个节点以及它的next指针指向
                //的位置是正确的
                ListNode* nxt=p0->next;//记录p0的下一个移动位置
                p0->next->next=cur;//记录反转的那一组节点的最后一个节点的next
                p0->next=pre;//记录反转的那一组节点的第一个节点的next
                p0=nxt;//接着进行反转
            }
            return dummy->next;
        }
    };

//反转单链表
class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* pre=nullptr, *cur=head;
            while(cur)
            {
                ListNode* nxt=cur->next;
                cur->next=pre;
                pre=cur;
                cur=nxt;
            }
            return pre;
        }
    };


//反转给定区间的单链表left>0
class Solution {
    public:
        //反转并不是真的反转，只改变节点的next指针指向即可
        ListNode* reverseBetween(ListNode* head, int left, int right) {
            ListNode* dummy =new ListNode(-1,head);
            ListNode* p0=dummy,*pre=nullptr;
            for(int i=1;i<left;i++)p0=p0->next;
            ListNode* cur=p0->next;
            for(int i=0;i<right-left+1;i++)
            {
                ListNode* nxt=cur->next;
                cur->next=pre;
                pre=cur;
                cur=nxt;
            }
            p0->next->next=cur;
            p0->next=pre;
            return dummy->next;
        }
    };